The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of links (communication paths such as telephone or optical lines) and nodes (usually routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning tree rooted at any other node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately.
As a result, when a packet for a destination node arrives at a node (the “first node”), the first node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth. In some circumstances it is desirable to have more control over the route that a packet takes in which case “tunneling” can be used. According to this scheme if a node A receives a packet destined for node Z and for some reason it is desired that the packet should travel via node Y, under normal circumstances node A would have no control over this (unless Y was an adjacent node), as the route is dependent on the forwarding table generated as a result of the SPF at node A and any intermediate nodes as well. However node A can “tunnel” the packet to node Y by encapsulating the received packet within a packet having destination node Y and sending it to node Y which acts as the tunnel end point. When the packet is received at node Y it is decapsulated and Y then forwards the original packet to node Z according to its standard forwarding table. Yet further control is available using directed forwarding in which the encapsulated packet includes a specific instruction as to which neighboring node of the end point of the tunnel the encapsulated packet should be sent, which comprises the “release point”. One well-known type of tunneling is Internet Protocol (IP) tunneling, in which the outer L3 header is an IP header, and the payload that it carries is an IP payload. Examples of such tunneling include Generic Routing Encapsulation (GRE) and IP/IP tunneling.
Unfortunately typical implementation performance is about 50% of normal IP forwarding. This is because the router first has to process the outer IP header to recognize the packet as one that terminates locally. It then strips the outer header (s), and processes the inner (payload) packet, which it then forwards towards its destination. The forwarding router accordingly effectively has to forward two packets, the first to itself, and the performance drops accordingly. In some implementations a two-stage pipeline is used. In a two-stage pipeline, one processor or hardware forwarder processes the packet outer and passes the payload to another similar processor, which processes the payload. The first processor then gets a new packet from the interfaced process itself. This approach reduces the latency of packet forwarding to a single packet time. However this increases forwarding performance at the cost of additional hardware. In some other implementations a common second pipeline stage is used, which is itself a bottleneck.